package com.yzh.search;

/**
 * @author 于振晗
 * @title: TwoSearch
 * @description: TODO 二分查找
 * @date 2020年09月01日
 * @path com.yzh.search
 */
public class TwoSearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int binary = binary(arr, 100);
        System.out.println("下标为：" + binary);

        int binary1 = binary(arr, 8, 0, arr.length - 1);
        System.out.println(binary1);
    }

    //非递归实现
    public static int binary(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > key) {
                high = mid - 1;
            } else if (arr[mid] < key) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }


    //递归实现  二分查找
    public static int binary(int[] arr, int key, int low, int high) {
        if(low > high){
            return -1;
        }
        int mid = (low+high)/2;
        if(arr[mid] > key){
            return binary(arr,key,low,mid -1);
        }else if(arr[mid] < key){
            return binary(arr,key,mid+1,high);
        }else{
            return mid;
        }
    }


}
